public class demo2 {

    public ListNode partition(ListNode pHead, int x) {
        // write code here
        ListNode headA=new ListNode(0);
        ListNode tailA=headA;
        ListNode headB=new ListNode(0);
        ListNode tailB=headB;
        while(pHead!=null){
            if(pHead.val<x){
                tailA.next=pHead;
                tailA=tailA.next;
            }else{
                tailB.next=pHead;
                tailB=tailB.next;
            }
            pHead=pHead.next;
        }
        tailB.next=null;
        if(tailA==headA){
            return headB.next;
        }
        tailA.next=headB.next;
        return headA.next;
    }

static  class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}

    public static void main(String[] args) {
        
    }
}
